#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/8 20:56
# @USER    : Shengji He
# @File    : DivideTwoIntegers.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        """
        Given two integers dividend and divisor, divide two integers without using multiplication,
        division and mod operator.

        Return the quotient after dividing dividend by divisor.

        The integer division should truncate toward zero, which means losing its fractional part. For example,
        truncate(8.345) = 8 and truncate(-2.7335) = -2.

        Example 1:

            Input: dividend = 10, divisor = 3

            Output: 3

            Explanation: 10/3 = truncate(3.33333..) = 3.
        Example 2:

            Input: dividend = 7, divisor = -3

            Output: -2

            Explanation: 7/-3 = truncate(-2.33333..) = -2.
        Note:

            - Both dividend and divisor will be 32-bit signed integers.
            - The divisor will never be 0.
            - Assume we are dealing with an environment which could only store integers within the 32-bit signed
            integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1
             when the division result overflows.

        :param dividend: int
        :param divisor: int
        :return: int
        """
        # div_length = len(str(divisor)) + 1
        # sign = ['-',''][(divisor > 0 and dividend >= 0) or (divisor < 0 and dividend < 0)]
        # dividend = abs(dividend)
        # divisor = abs(divisor)
        # ans = 0
        # while divisor <= dividend:
        #     nums = list(str(dividend))
        #     # nums.reverse()
        #     i = 0
        #     quo = []    # 商
        #     rem = []
        #     while i < len(nums):
        #         ds = int(''.join(nums[i: i + div_length if (i + div_length) < len(nums) else len(nums)]))
        #         q = 0
        #         tl = len(nums[i: i + div_length if (i + div_length) < len(nums) else len(nums)])
        #         while divisor <= ds:
        #             ds = ds - divisor
        #             q += 1
        #         quo.append(('%0' + str(tl) + 'd') % q)
        #         rem.append(('%0' + str(tl) + 'd') % ds)
        #         i += div_length
        #     ans = ans + int(''.join(quo))
        #     dividend = int(''.join(rem))
        #     if len(str(dividend)) < div_length:
        #         div_length -= 1
        #
        # ans = int(sign + str(ans))
        # return [ans, 2 ** 31 -1][ans < - 2 ** 31 or ans > 2 ** 31 - 1]
        sign = (dividend > 0) ^ (divisor > 0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        count = 0
        #把除数不断左移，直到它大于被除数
        while dividend >= divisor:
            count += 1
            divisor <<= 1
        result = 0
        while count > 0:
            count -= 1
            divisor >>= 1
            if divisor <= dividend:
                result += 1 << count # 这里的移位运算是把二进制（第count+1位上的1）转换为十进制
                dividend -= divisor
        if sign: result = -result
        return result if -(1<<31) <= result <= (1<<31)-1 else (1<<31)-1


if __name__ == '__main__':
    S = Solution()
    # a = 7
    # a = -2147483648
    # b = 1
    # a = 2147483647
    # b = 2
    a = 123456
    b = 3
    print(S.divide(a, b))
    print('done')
